home *** CD-ROM | disk | FTP | other *** search
/ CICA 1995 September (Japanese) / CICA Shareware for Windows CD-ROM (Walnut Creek) (September 1995) (Japanese) (Disc 2).iso / disc2 / nt / source.exe / POSIX / GREP / EGREP.C < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-03  |  27.4 KB  |  1,134 lines
  1. /*
  2.      Hybrid Boyer/Moore/Gosper-assisted 'grep/egrep/fgrep' search, with delta0
  3.      table as in original paper (CACM, October, 1977).  No delta1 or delta2.
  4.      According to experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of
  5.      minimal practical value.  However, to improve for worst case input,
  6.      integrating the improved Galil strategies (Apostolico/Giancarlo, SIAM. J.
  7.      Comput., Feb. 1986) deserves consideration.
  8.  
  9.      Method:     extract longest metacharacter-free string from expression.
  10.         this is done using a side-effect from henry spencer's regcomp().
  11.         use boyer-moore to match such, then pass submatching lines
  12.         to either regexp() or standard 'egrep', depending on certain
  13.         criteria within execstrategy() below.  [this tradeoff is due
  14.         to the general slowness of the regexp() nondeterministic
  15.         machine on complex expressions, as well as the startup time
  16.         of standard 'egrep' on short files.]  alternatively, one may
  17.         change the vendor-supplied 'egrep' automaton to include
  18.         boyer-moore directly.  see accompanying writeup for discussion
  19.         of kanji expression treatment.
  20.  
  21.         late addition:  apply trickbag for fast match of simple
  22.         alternations (sublinear, in common low-cardinality cases).
  23.         trap fgrep into this lair.
  24.  
  25.         gnu additions:  -f, newline as |, \< and \> [in regexec()], more
  26.                 comments.  inspire better dfa exec() strategy.
  27.                 serious testing and help with special cases.
  28.  
  29.      Algorithm amalgam summary:
  30.  
  31.         dfa e?grep         (aho/thompson)
  32.         ndfa regexp()         (spencer/aho)
  33.         bmg            (boyer/moore/gosper)
  34.         "superimposed" bmg       (jaw)
  35.         fgrep            (aho/corrasick)
  36.  
  37.         sorry, but the knuth/morris/pratt machine, horspool's
  38.         "frequentist" code, and the rabin/karp matcher, however cute,
  39.         just don't cut it for this production.
  40.  
  41.      James A. Woods                Copyright (c) 1986
  42.      NASA Ames Research Center
  43. */
  44.  
  45. #include <stdio.h>
  46. #include <stdlib.h>
  47. #include <ctype.h>
  48. #include <fcntl.h>
  49. #include <string.h>
  50. #include <sys/types.h>
  51. #include <sys/stat.h>
  52. #if _POSIX_SOURCE
  53. # include <unistd.h>
  54. #endif
  55. #include "regexp.h"        /* must be henry spencer's version */
  56. #if WIN_NT
  57. # include "glob.h"
  58. #endif
  59.  
  60. #define    MIN(A, B)    ((A) > (B) ? (B) : (A))
  61.  
  62. #ifdef    SLOWSYS
  63. #define read    xread
  64. #endif
  65. /*
  66.  * define existing [ef]?grep program locations below for use by execvp().
  67.  * [execlp() would be used were it not for the possibility of
  68.  * installation-dependent recursion.] 
  69.  */
  70. #ifdef WIN_NT
  71. #define EGREPSTD    "/bin/egrep"
  72. #define    FGREPSTD    "/bin/fgrep"
  73. #endif
  74. #ifndef EGREPSTD
  75. #define    EGREPSTD    "/usr/bin/egrep"
  76. #endif
  77. #ifndef GREPSTD
  78. #define    GREPSTD        "/bin/grep"
  79. #endif
  80. #ifndef FGREPSTD
  81. #define    FGREPSTD    "/usr/bin/fgrep"
  82. #endif
  83.  
  84. #define BUFSIZE    8192        /* make higher for cray */
  85. #define PATSIZE 6000
  86. #define LARGE     BUFSIZE + PATSIZE
  87.  
  88. #define ALTSIZE    100        /* generous? */
  89. #define NALT    7        /* tied to scanf() size in alternate() */
  90. #define NMUSH    6        /* loosely relates to expected alt length */
  91.  
  92. #define    FIRSTFEW    10    /* Always do FIRSTFEW matches with regexec() */
  93. #define    PUNTPERCENT    5    /* After FIRSTFEW, if PUNTPERCENT of the input
  94.                  * was processed by regexp(), exec std egrep. */
  95. #define NL    '\n'
  96. #define    EOS    '\0'
  97. #define    NONASCII    0200    /* Bit mask for Kanji non-ascii chars */
  98. #define META    "\n^$.[]()?+*|\\"    /* egrep meta-characters */
  99. #define SS2    '\216'        /* EUC Katakana (or Chinese2) prefix */
  100. #define SS3    '\217'        /* EUC Kanji2 (or Chinese3) prefix */
  101.  
  102. #if __STDC__
  103. extern int getopt (int, char **, const char *);
  104. #else
  105. extern int getopt();
  106. #endif
  107. extern char *optarg;
  108. extern int optind;
  109. extern int optopt;
  110. char *progname;
  111.  
  112. int cflag, iflag, eflag, fflag, lflag, nflag;    /* SVID flags */
  113. int sflag, hflag;        /* v7, v8, bsd */
  114.  
  115. int firstflag;            /* Stop at first match */
  116. int grepflag;            /* Called as "grep" */
  117. int fgrepflag;            /* Called as "fgrep" */
  118. int egrepflag;            /* Called as neither "grep" nor "fgrep" */
  119. int altflag;            /* Simple alternation in pattern */
  120. int boyonly;            /* No regexp needed -- all simple */
  121. int flushflag;
  122. int grepold, egrepold, fgrepold;
  123.  
  124. int nalt;            /* Number of alternatives */
  125. int nsuccess;            /* 1 for match, 2 for error */
  126. int altmin;            /* Minimum length of all the alternate
  127.                  * strings */
  128. int firstfile;            /* argv index of first file argument */
  129. long nmatch;            /* Number of matches in this file */
  130. long incount, counted;        /* Amount of input consumed */
  131. long rxcount;            /* Bytes of input processed by regexec() */
  132. int boyfound;            /* accumulated partial matches (tripped by
  133.                  * FIRSTFEW) */
  134. int prevmatch;            /* next three lines aid fast -n */
  135. long nline, prevnline;
  136. char *prevloc;
  137.  
  138. regexp *rspencer;
  139. char *pattern;
  140. char *patboy;            /* Pattern for simple Boyer-Moore */
  141. char *patfile;            /* Filename containing pattern(s) */
  142.  
  143. int delta0[256];        /* Boyer-Moore algorithm core */
  144. char cmap[256];            /* Usually 0-255, but if -i, maps upper to
  145.                  * lower case */
  146. char str[BUFSIZE + 2];
  147. int nleftover;
  148. char linetemp[BUFSIZE];
  149. char altpat[NALT][ALTSIZE];    /* alternation component storage */
  150. int altlen[NALT];
  151. short altset[NMUSH + 1][256];
  152. char preamble[200];        /* match prefix (filename, line no.) */
  153.  
  154. int fd;
  155. #if __STDC__
  156. char *pfile (const char *);
  157. void egsecute (const char *);
  158. void chimaera (const char *, char *);
  159. char *linesave (char *, register int);
  160. char *submatch (const char *, char *, const char *, register const char *,
  161.     register char *, int);
  162. char *kanji (register const char *, register const char *, register char *);
  163. void gosper (const char *);
  164. char *gotamatch (register const char *, register char *);
  165. char *fold (const char *);
  166. int strindex (const char *, const char *);
  167. char *grepxlat (const char *);
  168. char *alternate (char *);
  169. void execstrategy (const char *);
  170. int nlcount (const char *, const char *);
  171. char *isolate (const char *);
  172. char *savematch (register char *);
  173. void flushmatches (void);
  174. void oops (const char *);
  175. void kernighan (char **);
  176. # if WIN_NT
  177. extern int globulate (int, int, char **);
  178. extern void deglobulate (void);
  179. extern int globulated_argc;
  180. extern char **globulated_argv;
  181. # endif
  182. #else
  183. char *
  184. grepxlat(), *fold(), *pfile(), *alternate(), *isolate();
  185. #endif
  186. char **args;
  187. #if WIN_NT
  188. pid_t ppid;
  189. int globulation;
  190. #endif
  191.  
  192. int
  193. #if __STDC__
  194. main (int argc, char **argv)
  195. #else
  196. main(argc, argv)
  197.     int argc;
  198.     char *argv[];
  199. #endif
  200. {
  201.     int c;
  202.     int errflag = 0;
  203.  
  204.     args = argv;
  205.  
  206. #if WIN_NT
  207.     ppid = getppid();
  208.     if ((progname = strrchr(argv[0], (ppid == (pid_t) 1) ? '\\' : '/')) != 0)
  209. #else
  210.     if ((progname = strrchr(argv[0], '/')) != 0)
  211. #endif
  212.         progname++;
  213.     else
  214.         progname = argv[0];
  215.     if (strcmp(progname, "grep") == 0)
  216.         grepflag++;
  217.     else if (strcmp(progname, "fgrep") == 0)
  218.         fgrepflag++;
  219.     else
  220.         egrepflag++;
  221.  
  222.     while ((c = getopt(argc, argv, "EFbchie:f:lnsvwxy1?")) != EOF) {
  223.         switch (c) {
  224.         case 'E':
  225.             if (!grepflag)
  226.                 ++errflag;
  227.             ++egrepflag;
  228.             continue;
  229.         case 'F':
  230.             if (!grepflag)
  231.                 ++errflag;
  232.             ++fgrepflag;
  233.             continue;
  234.         case 'f':
  235.             fflag++;
  236.             patfile = optarg;
  237.             continue;
  238.         case 'b':
  239.         case 'v':
  240.             egrepold++;    /* boyer-moore of little help here */
  241.             continue;
  242.         case 'c':
  243.             cflag++;
  244.             continue;
  245.         case 'e':
  246.             eflag++;
  247.             pattern = optarg;
  248.             continue;
  249.         case 'h':
  250.             hflag++;
  251.             continue;
  252.         case '1':    /* Stop at very first match */
  253.             firstflag++;    /* spead freaks only */
  254.             continue;
  255.         case 'i':
  256.             iflag++;
  257.             continue;
  258.         case 'l':
  259.             lflag++;
  260.             continue;
  261.         case 'n':
  262.             nflag++;
  263.             continue;
  264.         case 's':
  265.             sflag++;
  266.             continue;
  267.         case 'w':
  268.         case 'y':
  269.             if (egrepflag || fgrepflag)
  270.                 errflag++;
  271.             grepold++;
  272.             continue;
  273.         case 'x':    /* needs more work, like -b above */
  274.             if (!fgrepflag)
  275.                 errflag++;
  276.             fgrepold++;
  277.             continue;
  278.         case '?':
  279.             errflag++;
  280.         }
  281.     }
  282.     if (errflag || ((argc <= optind) && !fflag && !eflag)) {
  283.         if (grepflag)
  284. oops("usage: grep [-E | -F] [-bcihlnsvwy] [-e] pattern [file ...]");
  285.         else if (fgrepflag)
  286. oops("usage: fgrep [-bcilnv] {-f patfile | [-e] strings} [file ...]");
  287.         else        /* encourage SVID options, though we provide
  288.                  * others */
  289. oops("usage: egrep [-bcilnv] {-f patfile | [-e] pattern} [file ...]");
  290.     }
  291.     if (grepflag && (egrepflag || fgrepflag))
  292.         --grepflag;
  293. #if WIN_NT
  294.     if (ppid == (pid_t) 1) /* if parent is CMD.EXE */
  295.     {
  296.         globulation = globulate(optind, argc, argv);
  297. #if 0
  298.         (void) printf("globulate: %d\n", c);
  299. #endif
  300.         if (globulation == 0)
  301.         {
  302.             argc = globulated_argc;
  303.             argv = globulated_argv;
  304.             args = argv;
  305. #if 0
  306.             for (c = 0; c < argc; ++c)
  307.                 (void) printf("[%s] ", argv[c]);
  308.             (void) printf("NULL\n");
  309. #endif
  310.         }
  311.     }
  312. #endif
  313.     if (fflag)
  314.         pattern = pfile(patfile);
  315.     else if (!eflag)
  316.         pattern = argv[optind++];
  317.  
  318.     if ((argc - optind) <= 1)    /* Filename invisible given < 2 files */
  319.         hflag++;
  320.     if (pattern[0] == EOS)
  321.         oops("empty expression");
  322.     /*
  323.      * 'grep/egrep' merger -- "old" grep is called to handle: tagged
  324.      * exprs \( \), word matches \< and \>, -w and -y options, char
  325.      * classes with '-' at end (egrep bug?), and patterns beginning with
  326.      * an asterisk (don't ask why). otherwise, characters meaningful to
  327.      * 'egrep' but not to 'grep' are escaped; the entire expr is then
  328.      * passed to 'egrep'. 
  329.      */
  330.     if (grepflag && !grepold) {
  331.         if (strindex(pattern, "\\(") >= 0 ||
  332.             strindex(pattern, "\\<") >= 0 ||
  333.             strindex(pattern, "\\>") >= 0 ||
  334.             strindex(pattern, "-]") >= 0 ||
  335.             pattern[0] == '*')    /* grep bug */
  336.             grepold++;
  337.         else
  338.             pattern = grepxlat(pattern);
  339.     }
  340.     if (grepold || egrepold || fgrepold)
  341.         kernighan(argv);
  342.  
  343.     if (iflag)
  344.         strcpy(pattern, fold(pattern));
  345.     /*
  346.      * If the pattern is a plain string, just run boyer-moore. If it
  347.      * consists of meta-free alternatives, run "superimposed" bmg.
  348.      * Otherwise, find best string, and compile pattern for regexec(). 
  349.      */
  350.     if (strpbrk(pattern, META) == NULL) {    /* do boyer-moore only */
  351.         boyonly++;
  352.         patboy = pattern;
  353.     } else {
  354.         if ((patboy = alternate(pattern)) != NULL)
  355.             boyonly++;
  356.         else {
  357.             if ((patboy = isolate(pattern)) == NULL)
  358.                 kernighan(argv);    /* expr too involved */
  359. #ifndef NOKANJI
  360.             for (c = 0; pattern[c] != EOS; c++)
  361.                 if (pattern[c] & NONASCII)    /* kanji + meta */
  362.                     kernighan(argv);
  363. #endif
  364.             if ((rspencer = regcomp(pattern)) == NULL)
  365.                 oops("regcomp failure");
  366.         }
  367.     }
  368.     gosper(patboy);        /* "pre-conditioning is wonderful"
  369.                  * -- v. strassen */
  370.  
  371.     if ((firstfile = optind) >= argc) {
  372.         /* Grep standard input */
  373.         if (lflag) {    /* We don't know its name! */
  374. #if WIN_NT
  375.             if (ppid == (pid_t) 1 && globulation == 0)
  376.                 deglobulate();
  377. #endif
  378.             exit(1);
  379.         }
  380.         egsecute((char *) NULL);
  381.     } else {
  382.         while (optind < argc) {
  383.             egsecute(argv[optind]);
  384.             optind++;
  385.             if (firstflag && (nsuccess == 1))
  386.                 break;
  387.         }
  388.     }
  389. #if WIN_NT
  390.     if (ppid == (pid_t) 1 && globulation == 0)
  391.         deglobulate();
  392. #endif
  393.     return (nsuccess == 2) ? 2 : (nsuccess == 0);
  394. }
  395.  
  396. char *
  397. #if __STDC__
  398. pfile (const char *pfname)
  399. #else
  400. pfile(pfname)            /* absorb expression from file */
  401.     char *pfname;
  402. #endif
  403. {
  404.     FILE *pf;
  405.     struct stat patstat;
  406.     static char *pat;
  407.  
  408.     if ((pf = fopen(pfname, "r")) == NULL)
  409.         oops("can't read pattern file");
  410.     if (fstat(fileno(pf), &patstat) != 0)
  411.         oops("can't stat pattern file");
  412.     if (patstat.st_size > PATSIZE) {
  413.         if (fgrepflag) {    /* defer to unix version */
  414.             fgrepold++;
  415.             return "dummy";
  416.         } else
  417.             oops("pattern file too big");
  418.     }
  419. #if __STDC__
  420.     if ((pat = malloc((size_t) patstat.st_size + 1)) == NULL)
  421.         oops("out of memory to read pattern file");
  422.     if (patstat.st_size !=
  423.         (off_t) fread(pat, sizeof(char), (size_t) patstat.st_size + 1, pf))
  424.         oops("error reading pattern file");
  425. #else
  426.     if ((pat = malloc((unsigned) patstat.st_size + 1)) == NULL)
  427.         oops("out of memory to read pattern file");
  428.     if (patstat.st_size !=
  429.         fread(pat, sizeof(char), patstat.st_size + 1, pf))
  430.         oops("error reading pattern file");
  431. #endif
  432.     (void) fclose(pf);
  433.  
  434.     pat[patstat.st_size] = EOS;
  435.     if (pat[patstat.st_size - 1] == NL)    /* NOP for egrep; helps grep */
  436.         pat[patstat.st_size - 1] = EOS;
  437.  
  438.     if (nlcount(pat, &pat[patstat.st_size]) > NALT) {
  439.         if (fgrepflag)
  440.             fgrepold++;    /* "what's it all about, alfie?" */
  441.         else
  442.             egrepold++;
  443.     }
  444.     return (pat);
  445. }
  446.  
  447. void
  448. #if __STDC__
  449. egsecute (const char *file)
  450. #else
  451. egsecute(file)
  452.     char *file;
  453. #endif
  454. {
  455.     if (file == NULL)
  456.         fd = 0;
  457. #ifndef O_RDONLY
  458. # define O_RDONLY 0
  459. #endif
  460.     else if ((fd = open(file, O_RDONLY)) <= 0) {
  461.         fprintf(stderr, "%s: can't open %s\n", progname, file);
  462.         nsuccess = 2;
  463.         return;
  464.     }
  465.     chimaera(file, patboy);
  466.  
  467.     if (!boyonly && !flushflag && file != NULL)
  468.         flushmatches();
  469.     if (file != NULL)
  470.         close(fd);
  471. }
  472.  
  473. void
  474. #if __STDC__
  475. chimaera (const char *file, char *pat)
  476. #else
  477. chimaera(file, pat)        /* "reach out and boyer-moore search someone" */
  478.     char *file, *pat;    /* -- soon-to-be-popular bumper sticker */
  479. #endif
  480. {
  481.     register char *k, *strend, *s;
  482.     register int j, count;
  483.     register int *deltazero = delta0;
  484.     int patlen = altmin;
  485.     char *t;
  486. #if !__STDC__
  487.     char *gotamatch(), *kanji(), *linesave(), *submatch();
  488. #endif
  489.  
  490.     nleftover = boyfound = flushflag = 0;
  491.     nline = 1L;
  492.     prevmatch = 0;
  493.     nmatch = counted = rxcount = 0L;
  494.  
  495.     while ((count = (int) read(fd, str + nleftover, BUFSIZE - nleftover)) > 0) {
  496.  
  497.         counted += count;
  498.         strend = linesave(str, count);
  499.  
  500.         for (k = str + patlen - 1; k < strend;) {
  501.             /*
  502.              * for a large class of patterns, upwards of 80% of
  503.              * match time is spent on the next line.  we beat
  504.              * existing microcode (vax 'matchc') this way. 
  505.              */
  506.             while ((k += deltazero[*(unsigned char *) k]) < strend);
  507.             if (k < (str + LARGE))
  508.                 break;
  509.             k -= LARGE;
  510.  
  511.             if (altflag) {
  512.                 /*
  513.                  * Parallel Boyer-Moore.  Check whether each
  514.                  * of the previous <altmin> chars COULD be
  515.                  * from one of the alternative strings. 
  516.                  */
  517.                 s = k - 1;
  518.                 j = altmin;
  519.                 while (altset[--j][(unsigned char)
  520.                          cmap[*(unsigned char *) s--]]);
  521.                 /*
  522.                  * quick test fails. in this life, compare
  523.                  * 'em all.  but, a "reverse trie" would
  524.                  * attenuate worst case (linear w/delta2?). 
  525.                  */
  526.                 if (--j < 0) {
  527.                     count = nalt - 1;
  528.                     do {
  529.                         s = k;
  530.                         j = altlen[count];
  531.                         t = altpat[count];
  532.  
  533.                         while
  534.                             (cmap[*(unsigned char *) s--]
  535.                              == t[--j]);
  536.                         if (j < 0)
  537.                             break;
  538.                     }
  539.                     while (count--);
  540.                 }
  541.             } else {
  542.                 /* One string -- check it */
  543.                 j = patlen - 1;
  544.                 s = k - 1;
  545.                 while (cmap[*(unsigned char *) s--] == pat[--j]);
  546.             }
  547.             /*
  548.              * delta-less shortcut for literati. short shrift for
  549.              * genetic engineers? 
  550.              */
  551.             if (j >= 0) {
  552.                 k++;    /* no match; restart next char */
  553.                 continue;
  554.             }
  555.             k = submatch(file, pat, str, strend, k, count);
  556.             if (k == NULL)
  557.                 return;
  558.         }
  559.         if (nflag) {
  560.             if (prevmatch)
  561.                 nline = prevnline + nlcount(prevloc, k);
  562.             else
  563.                 nline = nline + nlcount(str, k);
  564.             prevmatch = 0;
  565.         }
  566.         strncpy(str, linetemp, nleftover);
  567.     }
  568.     if (cflag) {
  569.         /* Bug from old grep: -c overrides -h.  We fix the bug. */
  570.         if (!hflag)
  571.             printf("%s:", file);
  572.         printf("%ld\n", nmatch);
  573.     }
  574. }
  575.  
  576. char *
  577. #if __STDC__
  578. linesave (char *str, register int count)
  579. #else
  580. linesave(str, count)        /* accumulate partial line at end of buffer */
  581.     char str[];
  582.     register int count;
  583. #endif
  584. {
  585.     register int j;
  586.  
  587.     count += nleftover;
  588.     if (count != BUFSIZE && fd != 0)
  589.         str[count++] = NL;    /* insurance for broken last line */
  590.     str[count] = EOS;
  591.     for (j = count - 1; str[j] != NL && j >= 0;)
  592.         j--;
  593.     /*
  594.      * break up these lines: long line (> BUFSIZE), last line of file, or
  595.      * short return from read(), as from tee(1) input 
  596.      */
  597.     if (j < 0 && (count == (BUFSIZE - nleftover))) {
  598.         str[count++] = NL;
  599.         str[count] = EOS;
  600.         linetemp[0] = EOS;
  601.         nleftover = 0;
  602.         return (str + count);
  603.     } else {
  604.         nleftover = count - j - 1;
  605.         strncpy(linetemp, str + j + 1, nleftover);
  606.         return (str + j);
  607.     }
  608. }
  609.  
  610. /*
  611.  * Process partial match. First check for mis-aligned Kanji, then match line
  612.  * against full compiled r.e. if statistics do not warrant handing off to
  613.  * standard egrep. 
  614.  */
  615. char *
  616. #if __STDC__
  617. submatch (const char *file, char *pat, const char *str,
  618.     register const char *strend, register char *k, int altindex)
  619. #else
  620. submatch(file, pat, str, strend, k, altindex)
  621.     char file[], pat[], str[];
  622.     register char *strend, *k;
  623.     int altindex;
  624. #endif
  625. {
  626.     register char *s;
  627.     char *t, c;
  628.  
  629.     t = k;
  630.     s = ((altflag) ? k - altlen[altindex] + 1 : k - altmin + 1);
  631. #ifndef NOKANJI
  632. # if WIN_NT
  633.     if (altflag)
  634.         c = altpat[altindex][0];
  635.     else
  636.         c = pat[0];
  637. # else
  638.     c = ((altflag) ? altpat[altindex][0] : pat[0]);
  639. # endif
  640.     if (c & NONASCII)
  641.         if ((s = kanji(str, s, k)) == NULL)
  642.             return (++k);    /* reject false kanji */
  643. #endif
  644.     do;
  645.     while (*s != NL && --s >= str);
  646.     k = s + 1;        /* now at line start */
  647.  
  648.     if (boyonly)
  649.         return (gotamatch(file, k));
  650.  
  651.     incount = counted - (strend - k);
  652.     if (boyfound++ == FIRSTFEW)
  653.         execstrategy(file);
  654.  
  655.     s = t;
  656.     do
  657.         rxcount++;
  658.     while (*s++ != NL);
  659.     *--s = EOS;
  660.     /*
  661.      * "quick henry -- the flit" (after theodor geisel) 
  662.      */
  663.     if (regexec(rspencer, ((iflag) ? fold(k) : k)) == 1) {
  664.         *s = NL;
  665.         if (gotamatch(file, k) == NULL)
  666.             return (NULL);
  667.     }
  668.     *s = NL;
  669.     return (s + 1);
  670. }
  671.  
  672. /*
  673.  * EUC code disambiguation -- scan backwards to first 7-bit code, while
  674.  * counting intervening 8-bit codes.  If odd, reject unaligned Kanji pattern. 
  675.  * SS2/3 checks are for intermixed Japanase Katakana or Kanji2. 
  676.  */
  677. char *
  678. #if __STDC__
  679. kanji (register const char *str, register const char *s, register char *k)
  680. #else
  681. kanji(str, s, k)
  682.     register char *str, *s, *k;
  683. #endif
  684. {
  685.     register int j = 0;
  686.  
  687.     for (s--; s >= str; s--) {
  688.         if (*s == SS2 || *s == SS3 || (*s & NONASCII) == 0)
  689.             break;
  690.         j++;
  691.     }
  692. #ifndef CHINESE
  693.     if (*s == SS2)
  694.         j -= 1;
  695. #endif /* CHINESE */
  696.     return ((j & 01) ? NULL : k);
  697. }
  698.  
  699. /*
  700.  * Compute "Boyer-Moore" delta table -- put skip distance in delta0[c] 
  701.  */
  702. void
  703. #if __STDC__
  704. gosper (const char *pattern)
  705. #else
  706. gosper(pattern)
  707.     char *pattern;        /* ... HAKMEM lives ... */
  708. #endif
  709. {
  710.     register int i, j;
  711.     unsigned char c;
  712.  
  713.     /* Make one-string case look like simple alternatives case */
  714.     if (!altflag) {
  715.         nalt = 1;
  716.         altmin = altlen[0] = strlen(pattern);
  717.         strcpy(altpat[0], pattern);
  718.     }
  719.     /* For chars that aren't in any string, skip by string length. */
  720.     for (j = 0; j < 256; j++) {
  721.         delta0[j] = altmin;
  722.         cmap[j] = (char) j;    /* Sneak in initialization of cmap */
  723.     }
  724.  
  725.     /* For chars in a string, skip distance from char to end of string. */
  726.     /* (If char appears more than once, skip minimum distance.) */
  727.     for (i = 0; i < nalt; i++)
  728.         for (j = 0; j < altlen[i] - 1; j++) {
  729.             c = altpat[i][j];
  730.             delta0[c] = MIN(delta0[c], altlen[i] - j - 1);
  731.             if (iflag && islower((int) c))
  732.                 delta0[toupper((int) c)] = delta0[c];
  733.         }
  734.  
  735.     /* For last char of each string, fall out of search loop. */
  736.     for (i = 0; i < nalt; i++) {
  737.         c = altpat[i][altlen[i] - 1];
  738.         delta0[c] = LARGE;
  739.         if (iflag && islower((int) c))
  740.             delta0[toupper((int) c)] = LARGE;
  741.     }
  742.     if (iflag)
  743.         for (j = 'A'; j <= 'Z'; j++)
  744.             cmap[j] = (char) tolower((int) j);
  745. }
  746.  
  747. /*
  748.  * Print, count, or stop on full match. Result is either the location for
  749.  * continued search, or NULL to stop. 
  750.  */
  751. char *
  752. #if __STDC__
  753. gotamatch (register const char *file, register char *s)
  754. #else
  755. gotamatch(file, s)
  756.     register char *file, *s;
  757. #endif
  758. {
  759. #if !__STDC__
  760.     char *savematch();
  761. #endif
  762.     int squirrel = 0;    /* nonzero to squirrel away FIRSTFEW matches */
  763.  
  764.     nmatch++;
  765.     nsuccess = 1;
  766.     if (!boyonly && boyfound <= FIRSTFEW && file != NULL)
  767.         squirrel = 1;
  768.  
  769.     if (sflag)
  770.         return (NULL);    /* -s usurps all flags (unlike some versions) */
  771.     if (cflag) {        /* -c overrides -l, we guess */
  772.         do;
  773.         while (*s++ != NL);
  774.     } else if (lflag) {
  775.         puts(file);
  776.         return (NULL);
  777.     } else {
  778.         if (!hflag)
  779.             if (!squirrel)
  780.                 printf("%s:", file);
  781.             else
  782.                 sprintf(preamble, "%s:", file);
  783.         if (nflag) {
  784.             if (prevmatch)
  785.                 prevnline = prevnline + nlcount(prevloc, s);
  786.             else
  787.                 prevnline = nline + nlcount(str, s);
  788.             prevmatch = 1;
  789.  
  790.             if (!squirrel)
  791.                 printf("%ld:", prevnline);
  792.             else
  793.                 sprintf(preamble + strlen(preamble),
  794.                     "%ld:", prevnline);
  795.         }
  796.         if (!squirrel) {
  797.             do
  798.                 putchar(*s);
  799.             while (*s++ != NL);
  800.         } else
  801.             s = savematch(s);
  802.  
  803.         if (nflag)
  804.             prevloc = s - 1;
  805.     }
  806.     return ((firstflag && !cflag) ? NULL : s);
  807. }
  808.  
  809. char *
  810. #if __STDC__
  811. fold (const char *line)
  812. #else
  813. fold(line)
  814.     char *line;
  815. #endif
  816. {
  817.     static char fline[BUFSIZE];
  818. #if __STDC__
  819.     register const char *s;
  820.     register char *t = fline;
  821. #else
  822.     register char *s, *t = fline;
  823. #endif
  824.  
  825.     for (s = line; *s != EOS; s++)
  826. #if WIN_NT
  827.         if (isupper((int) *s))
  828.             *t++ = (char) tolower((int) *s);
  829.         else
  830.             *t++ = *s;
  831. #else
  832.         *t++ = (isupper((int) *s) ? (char) tolower((int) *s) : *s);
  833. #endif
  834.     *t = EOS;
  835.     return (fline);
  836. }
  837.  
  838. int
  839. #if __STDC__
  840. strindex (const char *s, const char *t)
  841. #else
  842. strindex(s, t)            /* the easy way, as in K&P, p. 192 */
  843.     char *s, *t;
  844. #endif
  845. {
  846.     int i, n;
  847.  
  848.     n = strlen(t);
  849.     for (i = 0; s[i] != '\0'; i++)
  850.         if (strncmp(s + i, t, n) == 0)
  851.             return (i);
  852.     return (-1);
  853. }
  854.  
  855. char *
  856. #if __STDC__
  857. grepxlat (const char *pattern)        /* grep pattern meta conversion */
  858. #else
  859. grepxlat(pattern)        /* grep pattern meta conversion */
  860.     char *pattern;
  861. #endif
  862. {
  863. #if __STDC__
  864.     register const char *p;
  865.     register char *s;
  866. #else
  867.     register char *p, *s;
  868. #endif
  869.     static char newpat[BUFSIZE];
  870.  
  871.     for (s = newpat, p = pattern; *p != EOS;) {
  872.         if (*p == '\\') {    /* skip escapes ... */
  873.             *s++ = *p++;
  874.             if (*p)
  875.                 *s++ = *p++;
  876.         } else if (*p == '[') {    /* ... and char classes */
  877.             while (*p != EOS && *p != ']')
  878.                 *s++ = *p++;
  879.         } else if (strchr("+?|()", *p) != NULL) {
  880.             *s++ = '\\';    /* insert protection */
  881.             *s++ = *p++;
  882.         } else
  883.             *s++ = *p++;
  884.     }
  885.     *s = EOS;
  886.     return (newpat);
  887. }
  888.  
  889. /*
  890.  * Test for simple alternation.  Result is NULL if it's not so simple, or is
  891.  * a pointer to the first string if it is. Warning:  sscanf size is a
  892.  * fixpoint, beyond which the speedup linearity starts to break down.  In the
  893.  * wake of the elegant aho/corrasick "trie"-based fgrep, generalizing
  894.  * altpat[] to arbitrary size is not useful. 
  895.  */
  896. char *
  897. #if __STDC__
  898. alternate (char *regexpr)
  899. #else
  900. alternate(regexpr)
  901.     char *regexpr;
  902. #endif
  903. {
  904.     register i, j, min;
  905.     unsigned char c;
  906.     char oflow[100];
  907.  
  908.     if (fgrepflag && strchr(regexpr, '|'))
  909.         return (NULL);
  910.  
  911.     i = strlen(regexpr);
  912.     for (j = 0; j < i; j++)
  913.         if (regexpr[j] == NL)
  914.             regexpr[j] = '|';
  915.  
  916.     if (!fgrepflag) {
  917.         if (strchr(regexpr, '|') == NULL || regexpr[0] == '|')
  918.             return (NULL);
  919.         if (strpbrk(regexpr, "^$.[]()?+*\\") != NULL
  920.             || strindex(regexpr, "||") >= 0)
  921.             return (NULL);
  922.     }
  923.     oflow[0] = EOS;
  924.     nalt = sscanf(regexpr, "%[^|]|%[^|]|%[^|]|%[^|]|%[^|]|%[^|]|%[^|]|%[^|]",
  925.               altpat[0], altpat[1], altpat[2], altpat[3], altpat[4], altpat[5], altpat[6], oflow);
  926.  
  927.     if (nalt < 1 || oflow[0] != EOS)
  928.         return (NULL);
  929.  
  930.     altmin = NMUSH;
  931.     for (j = 0; j < nalt; j++) {
  932.         min = altlen[j] = strlen(altpat[j]);
  933.         if (min > ALTSIZE)
  934.             return (NULL);
  935.         altmin = MIN(altmin, min);
  936.     }
  937.     if (nalt > 1) {        /* build superimposed "pre-match" sets per
  938.                  * char */
  939.         altflag++;
  940.         for (j = 0; j < nalt; j++)
  941.             for (i = 0; i < altmin; i++) {
  942.                 c = altpat[j][altlen[j] - altmin + i];
  943.                 altset[i + 1][c] = 1;    /* offset for sentinel */
  944.             }
  945.     }
  946.     return (altpat[0]);
  947. }
  948.  
  949. /*
  950.  * Grapple with the dfa (std egrep) vs. ndfa (regexp) tradeoff. Criteria to
  951.  * determine whether to use dfa-based egrep:  We do FIRSTFEW matches with
  952.  * regexec().  Otherwise, if Boyer-Moore up to now matched more than
  953.  * PUNTPERCENT of the input, and there is sufficient bulk remaining to
  954.  * justify justify a process exec, do old *grep, presuming that its greater
  955.  * speed at regular expressions will pay us back over this volume.  At
  956.  * FIRSTFEW, dump the saved matches collected by savematch(). They are saved
  957.  * so that a "PUNT" can "rewind" to ignore them.  Stdin is problematic,
  958.  * since it's hard to rewind. 
  959.  */
  960.  
  961. #define CTHRESH    50000
  962.  
  963. void
  964. #if __STDC__
  965. execstrategy (const char *file)
  966. #else
  967. execstrategy(file)
  968.     char *file;
  969. #endif
  970. {
  971.     struct stat stbuf;
  972.     int pctmatch;
  973.     long cremain;
  974.  
  975.     pctmatch = (int) ((100 * rxcount) / incount);
  976.     if (!grepflag && pctmatch > PUNTPERCENT && file != NULL) {
  977.         fstat(fd, &stbuf);
  978.         cremain = stbuf.st_size - incount;
  979.         if (cremain > CTHRESH)
  980.             kernighan(args);
  981.     }
  982.     if (file != NULL)
  983.         flushmatches();
  984. }
  985.  
  986. int
  987. #if __STDC__
  988. nlcount (const char *bstart, const char *bstop)        /* flail interval to totalize newlines. */
  989. #else
  990. nlcount(bstart, bstop)        /* flail interval to totalize newlines. */
  991.     char *bstart, *bstop;
  992. #endif
  993. {
  994. #if __STDC__
  995.     register const char *s = bstart;
  996.     register const char *t = bstop;
  997. #else
  998.     register char *s = bstart;
  999.     register char *t = bstop;
  1000. #endif
  1001.     register int count = 0;
  1002.  
  1003.     do {            /* loop unroll for older architectures */
  1004.         if (*t == NL)    /* ... ask ames!jaw for sample code */
  1005.             count++;
  1006.     } while (t-- > s);
  1007.  
  1008.     return (count);
  1009. }
  1010.  
  1011. char *
  1012. #if __STDC__
  1013. isolate (const char *regexpr)        /* isolate longest metacharacter-free string */
  1014. #else
  1015. isolate(regexpr)        /* isolate longest metacharacter-free string */
  1016.     char *regexpr;
  1017. #endif
  1018. {
  1019.     char *dummyexpr;
  1020.  
  1021.     /*
  1022.      * We add (.)* because Henry's regcomp only figures regmust if it
  1023.      * sees a leading * pattern.  Foo! 
  1024.      */
  1025. #if __STDC__
  1026.     dummyexpr = malloc((size_t) strlen(regexpr) + 5);
  1027. #else
  1028.     dummyexpr = malloc((unsigned) strlen(regexpr) + 5);
  1029. #endif
  1030.     sprintf(dummyexpr, "(.)*%s", regexpr);
  1031.     if ((rspencer = regcomp(dummyexpr)) == NULL)
  1032.         kernighan(args);
  1033.     return (rspencer->regmust);
  1034. }
  1035.  
  1036. char *matches[FIRSTFEW];
  1037. static int mcount = 0;
  1038.  
  1039. char *
  1040. #if __STDC__
  1041. savematch (register char *s)            /* horde matches during statistics gathering */
  1042. #else
  1043. savematch(s)            /* horde matches during statistics gathering */
  1044.     register char *s;
  1045. #endif
  1046. {
  1047.     char *p;
  1048.     char *start = s;
  1049.     int msize = 0;
  1050.     int psize = strlen(preamble);
  1051.  
  1052.     while (*s++ != NL)
  1053.         msize++;
  1054.     *--s = EOS;
  1055.  
  1056. #if __STDC__
  1057.     p = malloc((size_t) msize + 1 + psize);
  1058. #else
  1059.     p = malloc((unsigned) msize + 1 + psize);
  1060. #endif
  1061.     strcpy(p, preamble);
  1062.     strcpy(p + psize, start);
  1063.     matches[mcount++] = p;
  1064.  
  1065.     preamble[0] = 0;
  1066.     *s = NL;
  1067.     return (s);
  1068. }
  1069.  
  1070. void
  1071. #if __STDC__
  1072. flushmatches (void)
  1073. #else
  1074. flushmatches()
  1075. #endif
  1076. {
  1077.     int n;
  1078.  
  1079.     flushflag = 1;
  1080.     for (n = 0; n < mcount; n++)
  1081.         printf("%s\n", matches[n]);
  1082.     mcount = 0;
  1083. }
  1084.  
  1085. void
  1086. #if __STDC__
  1087. oops (const char *message)
  1088. #else
  1089. oops(message)
  1090.     char *message;
  1091. #endif
  1092. {
  1093.     static const char usage[] = "usage: ";
  1094.  
  1095.     if (strncmp(message, usage, sizeof usage - 1) == 0)
  1096.         fprintf(stderr, "%s\n", message);
  1097.     else
  1098.         fprintf(stderr, "%s: %s\n", progname, message);
  1099. #if WIN_NT
  1100.     if (ppid == (pid_t) 1 && globulation == 0)
  1101.         deglobulate();
  1102. #endif
  1103.     exit((optopt == '?') ? 0 : 2);
  1104. }
  1105.  
  1106. void
  1107. #if __STDC__
  1108. kernighan (char **args)            /* "let others do the hard part ..." */
  1109. #else
  1110. kernighan(args)            /* "let others do the hard part ..." */
  1111.     char *args[];
  1112. #endif
  1113. {
  1114.     /*
  1115.      * We may have already run grep on some of the files; remove them
  1116.      * from the arg list we pass on.  Note that we can't delete them
  1117.      * totally because the number of file names affects the output
  1118.      * (automatic -h). 
  1119.      */
  1120.     /* better would be fork/exec per punted file -- jaw */
  1121.  
  1122.     while (firstfile && optind > firstfile)
  1123.         args[firstfile++] = "/dev/null";
  1124.  
  1125.     fflush(stdout);
  1126.  
  1127.     if (grepflag)
  1128.         execvp(GREPSTD, args), oops("can't exec old 'grep'");
  1129.     else if (fgrepflag)
  1130.         execvp(FGREPSTD, args), oops("can't exec old 'fgrep'");
  1131.     else
  1132.         execvp(EGREPSTD, args), oops("can't exec old 'egrep'");
  1133. }
  1134.